package com.zhulei.biji.suanfa.pace;

/**
 * @description:
 * @author: zhulei
 * @create: 2025-03-17 14:17
 **/
public class MinSwaps {
    /**
     * 给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。
     * <p>
     * 只有能满足下述所有条件的字符串才能称为 平衡字符串 ：
     * <p>
     * 字符串是一个空字符串，或者
     * 字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
     * 字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。
     * 你可以交换 任意 两个下标所对应的括号 任意 次数。
     * <p>
     * 返回使 s 变成 平衡字符串 所需要的 最小 交换次数。
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "][]["
     * 输出：1
     * 解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
     * 最终字符串变成 "[[]]" 。
     * 示例 2：
     * <p>
     * 输入：s = "]]][[["
     * 输出：2
     * 解释：执行下述操作可以使字符串变成平衡字符串：
     * - 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
     * - 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
     * 最终字符串变成 "[[][]]" 。
     * 示例 3：
     * <p>
     * 输入：s = "[]"
     * 输出：0
     * 解释：这个字符串已经是平衡字符串。
     * 提示：
     * <p>
     * n == s.length
     * 2 <= n <= 106
     * n 为偶数
     * s[i] 为'[' 或 ']'
     * 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2
     * Related Topics
     * 栈
     * 贪心
     * 双指针
     * 字符串
     * <p>
     * 👍 78
     * 👎 0
     */
    public static void main(String[] args) {
        String s = "]]][[[";
        System.out.println(minSwaps1(s));
    }

    public static int minSwaps(String s) {
        int[] cnt = new int[s.length()];
        int temp = 0, min = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '[') {
                temp++;
            } else {
                temp--;
            }
            min = Math.min(min, temp);
            cnt[i] = temp;
        }
        return (-min + 1) / 2;
    }

    public static char[] minSwaps1(String s) {
        char[] chars = s.toCharArray();
        int ans = 0;
        int c = 0;
        int j = chars.length - 1;
        for (int i = 0; i < chars.length; i++) {
            // 当c大于0说明 【 多，只需要往后继续i++就好，因为每个【 都有】做匹配
            if (chars[i] == '['){
                c++;
            }
            else if (c > 0){
                c--;
            }
            else {
                while (chars[j] == ']')
                    j--;
                chars[j] = ']';
                chars[i] = '[';
                c++;
                ans++;
            }
        }
        return chars;
    }
}


